package demo;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-23
 * Time: 13:16
 */
public class Heap {

    public int[] elem;//将堆中存放到数组中
    public int usedSize;//数组的有效个数

    public Heap(){
        this.elem = new int[10];
        this.usedSize =0;
    }

    //交换两个元素
    public void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //向下调整算法
    public void shiftDown(int[] array,int parent,int len){
        int child = 2*parent+1;
        while(child<len){
            //找左右孩子节点最大的值
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            //此时child就是左右孩子节点最大的
            //与父亲节点进行比较
            if(array[parent]<array[child]){
                swap(array,parent,child);
            }else {
               break;//并不需要进行交换这棵树已经是大根堆
            }
            parent = child;
            child = 2*parent+1;
        }
    }

    //建堆
    public void createHeap(int[] array){
        //将array数组元素都保存到elem数组中去
        for(int i =0;i<array.length;++i){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //通过找到最后一个父节点来进行向下调整
        for(int p = (this.usedSize-1-1)/2;p>=0;p--){
            shiftDown(this.elem,p,this.usedSize);
        }
    }

    //向上调整算法
    public void shiftUp(int child){
        int parent = (child-1)/2;//根据孩子节点推算出父节点
        while(parent>=0){//parent小于0则调整结束
            if(this.elem[child]>this.elem[parent]){
                swap(this.elem,parent,child);
            }else {
                break;
            }
            //更新父节点和子节点
            child = parent;
            parent = (child-1)/2;
        }
    }

    //增容
    public void grow(){
        this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    }

    //堆的插入
    public void offer(int key){
        if(this.elem.length==this.usedSize){
            grow();
        }
        //先将key插入到数组最后一个位置
        //然后再将key向上调整到合适位置使整个堆依然为大根堆
        this.elem[this.usedSize] = key;
        shiftUp(this.usedSize);
        this.usedSize++;
    }

    public boolean isEmpty(){
        return this.usedSize==this.elem.length;
    }

    public void poll(){
        if(isEmpty()){
            System.out.println("该堆为空不能删除");
            return ;
        }
        swap(this.elem,0,this.usedSize-1);
        shiftDown(this.elem,0,this.usedSize-1);
        this.usedSize--;
    }

}
